OUTLINE FOR ONR WORKSHOP ON
KNOWLEDGE-SYSTEMS SCIENCE AND ENGINEERING

   




The foundation of each of the projects to be covered in the workshop -- 
and subsequent book -- is expert knowledge. They must deal with its acquisition 
from practitioners, its accomodation into the existing data base, and its 
use to solve problems. Continued work on these topics provides new techniques 
and mechanisms for the design and construction of knowledge-based programs; 
 experiences gained from the actual construction of these systems then feeds 
back both (i) evaluative information on the ideas' utility and (ii) reports 
of quite specific problems and the ways in which they were overcome, which 
may suggest some more general method to be tried in other programs.  This 
is the cycle of development of core theory and individual projects that 
comprises the paradigm of our field today.


Below is an outline of the various aspects of current core research in  
knowledge systems science and engineering.  While not every project will 
have components along each of these dimensions, it will be useful for each 
participant to present the theoretical side of his contribution as a subset 
of this organization:

1. Knowledge Acquisition
	Ways in which new domain-dependent facts and rules of
		good judgment are obtained for the knowledge base.
	a. Extraction of facts and heuristics from experts; Learning by 
being told
	b. Automatic discovery of new facts and heuristics
2. Knowledge Accomodation
	Ways to represent and integrate new information (facts,
		heuristics, conjectures) into a growing knowledge base.
	a. Consistency among knowledge entered by an expert
	b. Consensus among knowledge entered by different experts
	c. Completeness of the knowledge base
		e.g., how a program can know what it does and doesn't know
	d. Discovery of new regularities (e.g. analogies) involving the 
new knowledge
	e. Representation of Knowledge (e.g., selecting an initial representation, 
change of
		representation, automatically extending schematized knowledge 
representations,...)
3. Knowledge Utilization
	Plausible reasoning, using inexact knowledge from an
 		incomplete, inconsistent knowledge base.
	a. Problem solving and other "classical" general frameworks for 
reasoning
	b. Scenario rationalization and other specialized inference procedures
	c. Theory formation
4. Knowledge Evaluation
	Meta-level information about the knowledge base itself
		and about the ways in which the program uses it.
	a. Scientific evaluation of the fruits of the core research
	b. Self-explanatory abilities possessed by each program
					.

[[IRA:  this will need to be refined and extended (e.g., you may wish to 
de-emphasize the expert nature of the systems whic the outline presumes); 
also, there must be another outline for the practical side of such projects, 
though that will have less potential for generalization and less timelessness 
than the above theoretical aspects.]]

Our objective is to investigate the nature of expert reasoning, both the 
knowledge used and the procedures for manipulating it.  By explicating the 
reasoning process in this way, by building a program  which carries out 
some task, it is "de-mystified": it is metamorphized from an art to
a science.  Ultimately,  the construction of such programs becomes itself 
a well-understood technical craft. 

At the moment, the building of expert systems is itself such an opaque art 
aspiring, through research efforts such as ours, to become a science.  One 
of the unifying themes of our research is the ultimate goal of understanding 
the techniques employed in building such programs. It has always been difficult 
to determine if a particular problem-solving method used in a particular 
knowledge-based program is domain-specific or whether it can generalize 
easily to other domains.  In current knowledge-based programs, the domain 
knowledge and the manipulation of it using AI techniques are often so intertwined 
that it is difficult to uncouple them, to make a program useful for another 
domain. 

The goal, then, is to isloate AI techniques that are general, to determine 
the conditions for their use.  
It is distant but worth pursuing. As just one use to which we would put 
such mastery if we had it, consider the construction of a very intelligent 
front end, which guides new package users to accomplish their tasks, which 
guides new system-modifiers to make changes in AI programs, and ultimately 
which guides system-designers in writing knowledge-based programs.  





1.  Knowledge Acquisition





Our research is predicated upon a body of assumptions which all point to 
knowledge as the appropriate focus, and to rule-based expert systems as 
the appropriate experimental vehicles: 
	(1) Humans continually face searches in more or less immense spaces; 
intelligence is the ability to bring appropriate knowledge to bear, to speed 
up such searching.  Increasing intelligence thus comprises (i) increasing 
the amount of knowledge posssessed, (ii) improving its organization, and 
(iii) refining the conditions for its applicability.
	(2) Intelligent systems can make the applicability of their knowledge 
explicit by representing it as condition-action (IF situation THEN appropriate-action) 
rules. Such pattern-directed inference systems can benefit from a schematized 
representation (frame, unit, being, actor, script, etc.) because this adds 
structure which the rule descriptions can exploit. [[FOOTNOTE: I.e., by 
a careful choice of slot types, the system builder can reduce most triggering 
conditions to simple checks on the state of various slots of specific units. 
Thus "If there are no known examples of disease X" can be coded as a quick 
null-check on the "Examples" slot of X's unit, rather than as an exhaustive 
search through an entire assertional database.]]




Extracting Facts & Heuristics from Experts

	Introduction

"Relevant" problem solving knowledge includes much formal and informal expertise 
of the domain expert; it also includes many mundane facts and figures that 
make up the elementary knowledge of the domain. Before a computer system 
can solve problems in the domain, this information must be transferred from 
the expert to the computer. 

Over the last decade, there has been some encouraging progress along this 
dimension. To build DENDRAL,  mass spectroscopy knowledge was added by a 
painstaking process over several years. By contrast,  PUFF was recently 
created in less than 50 hours of interaction with experts and with less 
than 10 man-weeks of effort by the knowledge engineers.  The main reason 
that the development was so rapid is that PUFF was built with the aid of 
an interactive knowledge engineering tool, EMYCIN. When knowledge engineers 
at the Heuristic Programming Project started the PUFF project, they already 
had a reasoning framework in which to fit the problem and an "English-like" 
language for expressing the diagnostic rules. The facilities that make EMYCIN 
such a powerful tool are the direct result of the core research over the 
last five years on the MYCIN program. 


 If, as we hope and expect, the coming decade sees a proliferation of knowledge-based 
assistant programs in diverse fields, it is essential to make the transfer 
of expertise from expert to program  a smooth, well-understood procedure. 
 Ideally, we would see experts building their own assistance programs, coached 
automatically to construct a usable knowledge base. Pulling the non-expert 
out of the system-building process will reduce the distortion of the expert's 
view of his world. But the domain expert should be free to devote his time 
to organizing the knowledge of his field, not to understanding some complex 
computer system. 

Contributors to this area should attempt to address some of the following 
eight research issues:  

	1.  How systems can provide on-line assistance (as opposed to reference 
to a printed instruction manual.)  A simple first step toward this is a 
facility to list and then describe the user's options at any point; more 
sophisticated would be some kind of teacher or knowledgable coach.

	2.  How systems should deal differently with the novice and experienced 
user, and more generally build up and employ schematized user models. 	 
	
	
	3.  In what kind of language should the user describe knowledge? 
 Our current hypothesis is that it should be one closely resembling his 
normal language. This does not necessarily mean a full natural language 
capability, because the language of experts is usually quite constrained. 
 This enhances the "readability" of the knowledge base by other experts. 
 

   	4.  Language is not always the best choice for inputting. How does 
the method of describing concepts (inputting new knowledge) depend on the 
type of the concept?  (E.g., the knowledge acquistion system should recognize 
that the most natural way for the expert to describe logical expressions 
is not also the best way of describing the structure of a chemical molecule.) 
 

 	5.  What kinds of routine documentation can the system take care 
of automatically for the user?.  E.g., record when and by whom knowledge 
about a particular entity was first described and subsequently modified.

	6.  Correcting and expanding the knowledge base is a large part 
of many users' tasks; in what ways can the system itself facilitate this 
process? 

	7. Computer scientists should not try to design interactive knowledge 
acquisition programs without the direct consultation of users.  Features 
that seem trivial or clever to one group may be vital or useless, respectively, 
to the other. To avoid this mismatch, how might the experts participate 
in the system design phase?

	8. Davis was surprised how rarely the Teiresias program's snappy 
advice like  "Every other rule relating to bacteremia mentioned culture 
site, why didn't you?" was welcome [ref]; Goldstein has reported similar 
needs for restraint [ref].  We apparently are just beginning to recognize 
rules of good judgment for automatic coaching, for giving advice to experts. 





Automatic Discovery of new facts and heuristics

One important  aspect of our core research outline is a focus on automated 
discovery.  An effort begun by HPP several years ago, Meta-Dendral [ref], 
was capable of inferring new rules of mass spectroscopy, given pairs of 
spectra and their correct identifications. A more recent effort resulted 
in a program, AM [ref], which defines new mathematical concepts, gathers 
empirical data about them, and notices regularities in that data.  Both 
projects pioneered the field of automatic theory formation, and have demonstrated 
its feasibility in widely disparate domains. 

Some of the issues which should be addressed by projects which fall into 
the Discovery category include:

	1. Open-ended discovery is inherently an exploration in an immense 
search space; how can knowledge be used to make this tractible? For example, 
AM used heuristic rules as plausible move generators, to suggest promising 
courses of action to follow next. But then the power of a system is limited 
by the heuristics we supply initially, unless:

	2. How can new heuristics themselves be discovered?   E.g., can 
heuristics be treated just like any other domain concepts?  

	3. What are the different types of learning, and the peculiarities 
of each?  E.g., learning by being told, by observing, by discovering, by 
proving, etc.

	4. What does the "space of heuristics" look like?  



2.  Knowledge Accomodation

One of the most fundamental problems facing the builder of a knowledge-based 
program is how to represent that knowledge. Statically, we can ask: What 
would a "snapshot" of the knowledge base at some instant look like?  More 
dynamically: How is new information integrated into the growing structure? 
 These are concrete research issues which we find outselves bumping against 
as the sizes of our program's knowledge bases grow larger and larger.

With a knowledge base of giant proportions, it is no longer feasible to 
exhaustively search through it while inferencing.  Rather, some structure 
must be imposed upon it, and that structure is then exploited to speed up 
the location of potentially relevant parts of the KB (knowledge base).  
Most current AI research efforts employ one or antoher variant of schematized 
representaion: the KB is structured into modules (units, frames, scripts, 
actors, beings, contract nets, personae, stereotypes, schemata) which have 
subdivisions (slots, facets, aspects, parts) which in turn may have subdivisions 
(subslots).  The use of such schematized representations is even more crucial 
for large expert systems based around heuristic rules:  by a judicious choice 
of slot (and subslot) types, most of the tests made in the conditions (IF-part) 
of heuristic rules can be reduced into trivial, quick checks on the state 
of some (sub)slot of some schema.  E.g.,  "If there are no known examples 
of disease X" can be coded as a quick null-check on the "Examples" slot 
of X's unit, rather than as an exhaustive search through an entire assertional 
database.

Among the issues such research is forced to deal with are:

	1. The consistency and validity of knowledge entered by an expert. 
 How he communicates his certainty to the system, and what it does if contradictory 
inputs are located. When and how should such contradictions be sought? In 
DENDRAL, an overall domain-specific matching function was used which reflected 
a priori probabilities of errors in the data.   More sophisticated answers 
are needed, though, as the magnitude of the knowledge base grows.  The issue 
is not whether reasoning can be effectively done even with an inconsistent 
knowledge base, but how to do it. The key observation is that for  very 
large, complex  knowledge bases, eliminating an inconsistent entry will 
frequently make the system perform worse, not better, in the long run.

	2. The consensus of knowledge among experts.  Often two eminent 
experts will disagree strongly on some rule of judgement, e.g. about which 
drug to administer for a particular infection, or about when to search formally 
for a proof versus spend time gathering examples.  Even though each expert 
may possess a set of heuristics which work well as a group, simply unioning 
their two sets may produce a body of heuristics which work at cross purposes 
and are much less effective than either was originally.  The more fortuitous 
converse case also occurs, namely the synergy that
can result when rules from two experts interact to produce something neither 
expert alone would have thought of.  Should consensus be sought?  If so, 
how?  When is it better to preserve disparity and try for the kind of synergy 
illustrated previously? 

	3. The completeness of the knowledge base.  How can an expert -- 
 and the system --  know what knowledge the system has and, perhaps much 
more critically, what information it doesn't possess.  One solution might 
be to have a strong model of the domain, a structured representation which 
makes it obvious when some gap in the knowledge exists, namely because some 
slot or other will be blank.  In most fields, experts will want to discriminate 
between (i) the absence of evidence and (ii) the evidence of absence.  

	4. What sorts of processing should be done when new data are entered, 
and what should be deferred?  This type of forward processing could include 
searching for ties to existing knowledge, computing what impact this knowledge 
would have had in prior situations, checking for consistency (and reconciling 
or initiating a dialogue if some inconsistency is noticed), checking for 
consensus, checking for analogies to existing knowledge, etc.  This is open-ended 
and data-driven -- not problem-solving at all, really, yet must be dealt 
with.

	5. Since knowledge representaion is so crucial, it would be very 
desirable to investigate such topics as initial selection of representation, 
communication of new representations to students, change of representation, 
extension of an existing representation, and discovery of new representations. 
 The state of knowledge about such topics is so limited that we expect most 
efforts reported on oby contributors to the workshop will be much more limited 
in scope.  E.g., the Eurisko project (successor to AM) is producing a language 
for defining new slot types out of old ones (e.g., as the composition, or 
the transitive closure, or the union,...), then permitting the program to 
explore new types of slots just as it is permitted to explore new definitions 
of mathematical concepts and new heuristics.

	6. Representing time-based knowledge.  Several problems which AI 
is currently working on involve situations  that evolve over time.  The 
basic issues  are (i) time-specified reference to objects and (ii) tracking 
causal changes on objects over time. [[IRA: we should probably generalize 
this to representing things which are awkward in KRL and other current units 
languages: including mass nouns, counterfactual conditionals, and all the 
other things that Bob Moore talked about last year.]]

	7. Grain Size in Complex Systems.	Among the virtues of production 
rules  are (i) their modularity allows easy addition and modification of 
inferential knowledge and (ii) they can be written in such a way that their 
grain size seems  appropriate for explanation systems.   As we move toward 
hierarchical reasoning methods the grain size of individual production rules 
seems too small for coherent explanations. Just as the reasoning methods 
work with abstractions to reduce the combinatorics, explanations of this 
should also be abstract. At present, the problem of factoring knowledge 
is an opaque art. When a frame-structured representation is used, a knowledge 
engineer makes decisions about what facts to group together.  This decision 
takes into account indexing during problem solving and the interactions 
among items in the knowledge base.  In hierarchical reasoning methods knowledge 
is viewed with a varying grain size;  it starts with an abstract conceptualization 
at the beginning of problem solving and  moves toward finer detail as the 
solution proceeds.   Although AI has some understanding of how to organize 
a body of knowledge hierarchically, much work remains to be done to make 
the best use of that organization during knowledge acquisition and problem 
solving. 

3.  Knowledge Usage


A knowledge based system comprises a knowledge base plus an inference engine. 
 Even those researchers who hold that the former deserves the most attention 
are nonetheless driven to experiment with the latter, with new forms of 
problem solving methods, with techniques of knowledge manipulation.

More specifically, they are studying such topics as cooperating knowledge 
sources (HSII-like) reasoning frameworks, opportunistic (best-first) agenda 
schedulers, reasoning with abstractions, orthogonal planning (planning about 
planning),  scenario rationalization (given a trace of some events, use 
a body of heuristic rules backwards to parse that scenario, to account for 
the event sequence and the results), inexact plausible reasoning, and other 
techniques. As we construct expert programs for increasingly knowledge-rich 
domains, the need increases to reason ever more symbolically about the justifications 
for their beliefs.

Some efforts concentrate upon the use of knowledge to form new theories 
and extend existing ones.   Issues to be dealt with here include: What characteristics 
make a domain more or less amenable to such automation?  How can hypotheses 
be evaluated, and how can such judgmental rules be improved gradually with 
experience?  When is it appropriate to employ plausible move generators, 
and when is it preferable to use heuristics as constratints on a legal move 
generator?  How can a problem solving program be extended to propose "interesting" 
new problems to attack? 




4.  Knowledge Evaluation

Once a knowledge-based system is built and used, a whole new source of information 
is available: meta-level judgments on the performance of that system.  The 
experts using the system in situ can feed back  evaluations as to its potency; 
scientists reading articles about its design can feed back theoretical evaluations 
as to its contributions to the field of knowledge engineering; the system 
itself can monitor its behavior, and can come up with self-descriptions, 
with explanations of why it chose some particular action to do at time x, 
patterns of its own behavioral patterns, etc.  


For programs upon which experts are relying in actual practice, AI researchers 
have found it very helpful to construct self-explanation subsystems.  An 
early example of this sort of capability was Winograd's SHRDLU program, 
which could answer Why? questions by tracing up its goal stack and How? 
questions by tracing down it.  In HPP programs, self-explanation systems 
so far employed have taken two basic forms:  canned text explicating rules 
[ref. to Prospector and/or to Lenat's PUP6 IJCAI4 article] and backtracking 
through rule invocation [ref. to Mycin and Teiresias].  Both explanation 
methods undeniably add to user confidence.  The improvement and extension 
of the existing two types is an important task which may well lead to new 
discoveries, and the design of new types of explanatory subsystems is under 
investigation (e.g., programs which represent their own entire control structure, 
which would enable them to interpretively introspect upon the minutae of 
their own behavior). Others are studying methods for modifying the level 
of explanation based on the abstractions used by the program and a model 
of the user.  
   
The act of explaining the knowledge has led to the problem of using the 
knowledge base for tutoring  purposes.  What are the rules of good judgment 
for presenting the contents of a knowledge base represented as a set of 
rules, and extending those methods  for relating to the user the contents 
of knowledge bases stored in  other representations?